{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Campus Bikes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: assignBikes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #校园自行车分配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在 X-Y 平面上表示的校园中，有 <code>n</code> 名工人和 <code>m</code> 辆自行车，其中 <code>n &lt;= m</code>。</p>\n",
    "\n",
    "<p>给定一个长度为 <code>n</code> 的数组&nbsp;<code>workers</code>&nbsp;，其中 <code>worker [i] = [xi, yi]</code>&nbsp;表示第 <code>i</code>&nbsp;个工人的位置。你也得到一个长度为 <code>m</code> 的自行车数组 <code>bikers</code> ，其中 <code>bikes[j] = [x<sub>j</sub>, y<sub>j</sub>]</code>&nbsp;是第 <code>j</code> 辆自行车的位置。所有给定的位置都是 <strong>唯一</strong> 的。</p>\n",
    "\n",
    "<p>我们需要为每位工人分配一辆自行车。在所有可用的自行车和工人中，我们选取彼此之间 <strong>曼哈顿距离</strong> 最短的工人自行车对&nbsp;<code>(worker<sub>i</sub>, bike<sub>j</sub>)</code>&nbsp;，并将其中的自行车分配給工人。</p>\n",
    "\n",
    "<p>如果有多个&nbsp;<code>(worker<sub>i</sub>, bike<sub>j</sub>)</code> 对之间的 <strong>曼哈顿距离</strong> 相同，那么我们选择 <strong>工人索引最小</strong> 的那对。类似地，如果有多种不同的分配方法，则选择 <strong>自行车索引最小</strong> 的一对。不断重复这一过程，直到所有工人都分配到自行车为止。</p>\n",
    "\n",
    "<p>返回长度为 <code>n</code> 的向量 <code>answer</code>，其中 <code>answer[i]</code>&nbsp;是第 <code>i</code>&nbsp;位工人分配到的自行车的索引（<strong>从 0 开始</strong>）。</p>\n",
    "\n",
    "<p>给定两点&nbsp;<code>p1</code>&nbsp;和&nbsp;<code>p2</code>&nbsp;之间的 <strong>曼哈顿距离</strong> 为&nbsp;<code>Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2019/03/06/1261_example_1_v2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]\n",
    "<strong>输出：</strong>[1,0]\n",
    "<strong>解释：</strong>工人 1 分配到自行车 0，因为他们最接近且不存在冲突，工人 0 分配到自行车 1 。所以输出是 [1,0]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2019/03/06/1261_example_2_v2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]\n",
    "<strong>输出：</strong>[0,2,1]\n",
    "<strong>解释：</strong>工人 0 首先分配到自行车 0 。工人 1 和工人 2 与自行车 2 距离相同，因此工人 1 分配到自行车 2，工人 2 将分配到自行车 1 。因此输出为 [0,2,1]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == workers.length</code></li>\n",
    "\t<li><code>m == bikes.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= m &lt;= 1000</code></li>\n",
    "\t<li><code>workers[i].length == bikes[j].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt; 1000</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>j</sub>, y<sub>j</sub>&nbsp;&lt; 1000</code></li>\n",
    "\t<li>所有工人和自行车的位置都<strong>不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [campus-bikes](https://leetcode.cn/problems/campus-bikes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [campus-bikes](https://leetcode.cn/problems/campus-bikes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[2,1]]\\n[[1,2],[3,3]]', '[[0,0],[1,1],[2,0]]\\n[[1,0],[2,2],[2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n=len(workers)\n",
    "        m=len(bikes)\n",
    "        state=(1<<m)\n",
    "        dp=[[float(\"inf\")]*state for _ in range(n+1)]\n",
    "        for j in range(state):\n",
    "            dp[0][j]=0\n",
    "        dis=[[float(\"inf\")]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                x,y=workers[i]\n",
    "                x1,y1=bikes[j]\n",
    "                dis[i][j]=abs(x-x1)+abs(y-y1)\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for s in range(state):\n",
    "                if bin(s).count(\"1\")!=(i-1):\n",
    "                    continue\n",
    "                for j in range(m):\n",
    "                    if s&(1<<j)==0:\n",
    "                        news=s|(1<<j)\n",
    "                        dp[i][news]=min(dp[i][news],dp[i-1][s]+dis[i-1][j])\n",
    "      #  print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n, m = len(workers), len(bikes)\n",
    "        dist = [[float('inf')] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                dist[i][j] = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]) \n",
    "        dp = [[float('inf')] * (1 << m) for _ in range(n+1)]\n",
    "        dp[0][0] = 0 \n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, 1 << m):\n",
    "                if str(bin(j)).count('1') == i:\n",
    "                    for k in range(m):\n",
    "                        if (j >> k) & 1:\n",
    "                            dp[i][j] = min(dp[i][j], dp[i-1][j^(1<<k)] + dist[i-1][k])\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n=len(workers)\n",
    "        m=len(bikes)\n",
    "        state=(1<<m)\n",
    " \n",
    "        dis=[[float(\"inf\")]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                x,y=workers[i]\n",
    "                x1,y1=bikes[j]\n",
    "                dis[i][j]=abs(x-x1)+abs(y-y1)\n",
    "        dp= [[float(\"inf\")]*state for _ in range(n+1)]\n",
    "\n",
    "        for s in range(state):\n",
    "            dp[0][s]=0\n",
    "        for i in range(1,n+1):\n",
    "            for s in range(state):\n",
    "                if bin(s).count(\"1\")==(i-1):\n",
    "                    for j in range(m):\n",
    "                        cur=1<<j\n",
    "                        if s&cur==0:\n",
    "                            news=s|cur\n",
    "                            dp[i][news]=min(dp[i][news],dp[i-1][s]+dis[i-1][j])\n",
    "\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def Manhattan(p1, p2):\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike):    # 对第 i 个人，搜索剩余的自行车并尝试分配给他，同时计算距离\n",
    "            if i == m:       # 如果没有人了，返回 0 \n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            for j in range(n):      # 遍历每个自行车\n",
    "                if bike & (1 << j) == 0:     # 如果未使用过\n",
    "                    # 把 bikes[j] 分配给 workers[i] 并计算距离 ，同时把人的已使用数量加 1、bike 的 mask 赋上值\n",
    "                    res = min(res, Manhattan(workers[i], bikes[j]) + dfs(i+1, bike | (1 << j))) \n",
    "            return res\n",
    "\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        # 记忆化搜索\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        def Manhattan(a,b):\n",
    "            return abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            # 表示给第i个工人选择自行车，已选择的自行车为集合pre，其曼哈顿距离和为dfs(i,pre)\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for j in range(m):\n",
    "                if pre & (1 << j) == 0:\n",
    "                    res = min(res,dfs(i+1,pre|(1 << j))+Manhattan(workers[i],bikes[j])) \n",
    "            return res\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m, n = len(workers), len(bikes)\n",
    "        def dist(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for j in range(n):\n",
    "                if bike & (1 << j) == 0:\n",
    "                    ans = min(ans, dfs(i + 1, bike | (1 << j)) + dist(workers[i], bikes[j]))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            x, y = workers[i]\n",
    "            for j in range(m):\n",
    "                if state & (1<<j):\n",
    "                    a, b = bikes[j]\n",
    "                    cur = abs(x-a)+abs(y-b) + dfs(i+1, state ^ (1<<j))\n",
    "                    res = min_(res, cur)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, (1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "      m,n=len(workers),len(bikes)\n",
    "      def getDis(w:List[int],b:List[int])->int:\n",
    "        return abs(w[0]-b[0])+abs(w[1]-b[1])\n",
    "      @cache\n",
    "      def dfs(cur:int,bike_use:int)->int:\n",
    "        if cur==m: return 0\n",
    "        res=float('inf')\n",
    "        for i in range(n):\n",
    "          if bike_use&(1<<i)==0:\n",
    "            res=min(res,getDis(workers[cur],bikes[i])+dfs(cur+1,bike_use|(1<<i)))\n",
    "        return res\n",
    "      return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def Manhattan(p1, p2):\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike): # 对第i个人，搜索剩余的自行车并尝试分配给他，同时计算距离\n",
    "            if i == m:  # 如果没有人了，返回 0 \n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            for j in range(n):      # 遍历每个自行车\n",
    "                if bike & (1 << j) == 0:   # 如果未使用过 \n",
    "                # 把 bikes[j] 分配给 workers[i] 并计算距离 ，同时把人的已使用数量加 1、bike 的 mask 赋上值\n",
    "                    res = min(res, Manhattan(workers[i], bikes[j]) + dfs(i+1, bike | (1 << j))) \n",
    "            return res\n",
    "\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return abs(workers[x][0]-bikes[y][0])+abs(workers[x][1]-bikes[y][1])\n",
    "        #状态压缩+记忆化搜索\n",
    "        n,m=len(workers),len(bikes)\n",
    "        #尝试给第i个工人分配自行车\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==n: return 0\n",
    "            res,cur=0,inf\n",
    "            for j in range(m):\n",
    "                if mask>>j&1:\n",
    "                    cur=min(cur,dfs(i+1,mask^(1<<j))+dis(i,j))\n",
    "            res+=cur\n",
    "            return res\n",
    "        return dfs(0,(1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return abs(workers[x][0]-bikes[y][0])+abs(workers[x][1]-bikes[y][1])\n",
    "        #状态压缩+记忆化搜索\n",
    "        n,m=len(workers),len(bikes)\n",
    "        #尝试给第i个工人分配自行车\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==n: return 0\n",
    "            res,cur=0,inf\n",
    "            for j in range(m):\n",
    "                if mask>>j&1:\n",
    "                    cur=min(cur,dfs(i+1,mask^(1<<j))+dis(i,j))\n",
    "            res+=cur\n",
    "            return res\n",
    "        return dfs(0,(1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return abs(workers[x][0]-bikes[y][0])+abs(workers[x][1]-bikes[y][1])\n",
    "        #状态压缩+记忆化搜索\n",
    "        n,m=len(workers),len(bikes)\n",
    "        #尝试给第i个工人分配自行车\n",
    "        #我们利用m位二进制数表达自行车的分配情况,1为可分配,0为已分配。\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==n: return 0\n",
    "            res,cur=0,inf\n",
    "            for j in range(m):\n",
    "                if mask>>j&1:\n",
    "                    cur=min(cur,dfs(i+1,mask^(1<<j))+dis(i,j))\n",
    "            res+=cur\n",
    "            return res\n",
    "        return dfs(0,(1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def Manhattan(a,b):\n",
    "            return abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for j in range(m):\n",
    "                if pre & (1 << j) == 0:\n",
    "                    res = min(res,dfs(i+1,pre|(1 << j))+Manhattan(workers[i],bikes[j]))\n",
    "            return res\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m, n = len(workers), len(bikes)\n",
    "        def dist(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for j in range(n):\n",
    "                if (bike >> j) & 1 == 0:\n",
    "                    ans = min(ans, dfs(i + 1, bike | (1 << j)) + dist(workers[i], bikes[j]))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.spatial.distance import cdist, cityblock\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        INF = 2 ** 31 - 1\n",
    "        d = cdist(workers, bikes, cityblock).astype(np.int64)\n",
    "        # dp\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        dp = [INF] * (1 << n)\n",
    "        for j in range(n):\n",
    "            dp[1 << j] = d[0, j]\n",
    "\n",
    "        minval = INF\n",
    "        for i in range(1, m):\n",
    "            # 前面已分配i个\n",
    "            # 遍历前面分配的状态\n",
    "            curr = (1 << i) - 1\n",
    "            while curr < len(dp):\n",
    "                for j in range(n):\n",
    "                    if (curr >> j) & 1 == 0:\n",
    "                        nstat = curr | (1 << j)\n",
    "                        dp[nstat] = min(dp[curr] + d[i, j], dp[nstat])\n",
    "                        if i == m - 1:\n",
    "                            minval = min(minval, dp[nstat])\n",
    "                lb = curr & -curr\n",
    "                r = curr + lb\n",
    "                curr = r | ((r ^ curr) // (lb * 4))\n",
    "        return int(minval)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m,n=len(workers),len(bikes)\n",
    "        workers.sort()\n",
    "        bikes.sort()\n",
    "        def calx(a,b,c,d):\n",
    "            return abs(a-c)+abs(b-d)\n",
    "        ans=float('inf')\n",
    "        @cache\n",
    "        def dfs(x,p,now):\n",
    "            #print(x,p,now)\n",
    "            nonlocal ans\n",
    "            if now>=ans:\n",
    "                return \n",
    "            if x==m:\n",
    "                ans=min(ans,now)\n",
    "                return\n",
    "            a,b=workers[x]\n",
    "            for i in range(n):\n",
    "                if (p>>i)&1:\n",
    "                    #p^=1<<i\n",
    "                    c,d=bikes[i]\n",
    "                    tmp=calx(a,b,c,d)\n",
    "                    dfs(x+1,p^(1<<i),now+tmp)\n",
    "        dfs(0,(1<<n)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.spatial.distance import cdist, cityblock\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        d = cdist(workers, bikes, cityblock)\n",
    "        r, c = linear_sum_assignment(d, False)\n",
    "        return int(d[r, c].sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m,n=len(workers),len(bikes)\n",
    "        workers.sort()\n",
    "        bikes.sort()\n",
    "        @cache\n",
    "        def calx(a,b,c,d):\n",
    "            return abs(a-c)+abs(b-d)\n",
    "        ans=float('inf')\n",
    "        @cache\n",
    "        def dfs(x,p,now):\n",
    "            #print(x,p,now)\n",
    "            nonlocal ans\n",
    "            if now>=ans:\n",
    "                return \n",
    "            if x==m:\n",
    "                ans=min(ans,now)\n",
    "                return\n",
    "            a,b=workers[x]\n",
    "            for i in range(n):\n",
    "                if (p>>i)&1:\n",
    "                    #p^=1<<i\n",
    "                    c,d=bikes[i]\n",
    "                    tmp=calx(a,b,c,d)\n",
    "                    dfs(x+1,p^(1<<i),now+tmp)\n",
    "        dfs(0,(1<<n)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "      workers_indexes = sorted(range(len(workers)), key=lambda i: workers[i])\n",
    "      bikes_indexes = sorted(range(len(bikes)), key=lambda i: bikes[i])\n",
    "      reader_indexes = [0] * len(workers)\n",
    "      heaps = [[] for _ in range(len(workers))]\n",
    "      result = [0 for _ in range(len(workers))]\n",
    "\n",
    "      heap = []\n",
    "      used = set()\n",
    "\n",
    "      def dist0(i,j):\n",
    "          worker = workers[i]\n",
    "\n",
    "          bike = bikes[j]\n",
    "          dist = abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])\n",
    "          return dist\n",
    "      def next_worker_dist(workers, bikes, heaps, bikes_indexes, reader_indexes, i):\n",
    "          worker = workers[i]\n",
    "\n",
    "          while reader_indexes[i] < len(bikes):\n",
    "              bike = bikes[bikes_indexes[reader_indexes[i]]]\n",
    "              if (not heaps[i] or bike[0] - worker[0] <= heaps[i][0][0]):\n",
    "                  dist = abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])\n",
    "                  heapq.heappush(heaps[i], (dist, i, bikes_indexes[reader_indexes[i]]))\n",
    "                  reader_indexes[i] += 1\n",
    "              else:\n",
    "                  break\n",
    "\n",
    "      for i, worker in enumerate(workers):\n",
    "          next_worker_dist(workers, bikes, heaps, bikes_indexes, reader_indexes, i)\n",
    "          heapq.heappush(heap, heapq.heappop(heaps[i]))\n",
    "\n",
    "      left_worker = len(workers)\n",
    "      while heap and left_worker > 0:\n",
    "          dist, i, j = heapq.heappop(heap)\n",
    "          if j not in used:\n",
    "              print(dist,i,j)\n",
    "              result[i]= j\n",
    "              used.add(j)\n",
    "              left_worker -= 1\n",
    "          else:\n",
    "              next_worker_dist(workers, bikes, heaps, bikes_indexes, reader_indexes, i)\n",
    "              heapq.heappush(heap, heapq.heappop(heaps[i]))\n",
    "\n",
    "      return result\n",
    "def assign_bikes(workers, bikes):\n",
    "    return Solution().assignBikes(workers,bikes)\n",
    "#assert [1,0]==Solution().assignBikes(workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]])\n",
    "#assert [0,2,1]==assign_bikes(workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]])\n",
    "r=Solution().assignBikes([[240,446],[745,948],[345,136],[341,68],[990,165],[165,580],[133,454],[113,527]], bikes = [[696,140],[95,393],[935,185],[767,205],[387,767],[214,960],[804,710],[956,307]])\n",
    "print(r)\n",
    "print([7,6,0,3,2,4,1,5])\n",
    "assert [7,6,0,3,2,4,1,5]==r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from bisect import insort_left\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "\n",
    "        A = []\n",
    "\n",
    "        for i, j in product(range(n), range(m)):\n",
    "            dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])\n",
    "    \n",
    "            A.append((dis, i, j))\n",
    "        \n",
    "        ans, vis1, vis2 = [0] * n, set(), set()\n",
    "        for dis, i, j in sorted(A):\n",
    "            if i not in vis1 and j not in vis2:\n",
    "                ans[i] = j\n",
    "                vis1.add(i)\n",
    "                vis2.add(j)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        import heapq\n",
    "        bikemem, workermem = set(), set()\n",
    "        mem = []\n",
    "        for _ in range(1998):\n",
    "            mem.append([])\n",
    "        ans = [0 for _ in range(len(workers))]\n",
    "        for i in range(len(workers)):\n",
    "            for j in range(len(bikes)):\n",
    "                dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])\n",
    "                heapq.heappush(mem[dist], [i, j])\n",
    "        for _ in range(1998):\n",
    "            tmp = mem[_]\n",
    "            while tmp:\n",
    "                x, y = heapq.heappop(tmp)\n",
    "                if x not in workermem and y not in bikemem:\n",
    "                    ans[x] = y\n",
    "                    workermem.add(x)\n",
    "                    bikemem.add(y)\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        mp=dict()\n",
    "        ans=[]\n",
    "        for i in range(len(workers)):\n",
    "            for j in range(len(bikes)):\n",
    "                worker=workers[i]\n",
    "                bike=bikes[j]\n",
    "                dist=abs(bike[0]-worker[0])+abs(bike[1]-worker[1])\n",
    "                if dist not in mp:\n",
    "                    mp[dist]=[]\n",
    "                mp[dist].append([i,j])\n",
    "        sort_mp=sorted(mp.keys())\n",
    "        bike_mark=[False for i in range(len(bikes))]\n",
    "        worker_mark=[False for i in range(len(workers))]\n",
    "        for key in sort_mp:\n",
    "            for (i,j) in mp[key]:\n",
    "                if bike_mark[j] is False and worker_mark[i] is False:\n",
    "                    worker_mark[i]=True\n",
    "                    bike_mark[j]=True\n",
    "                    ans.append([i,j])\n",
    "                else:\n",
    "                    continue\n",
    "        ans.sort()\n",
    "        res=[]\n",
    "        for a in ans:\n",
    "            res.append(a[1])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序+贪心\n",
    "    def assignBikes1(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        dis = []\n",
    "        for i in range(n):\n",
    "            a, b = workers[i]\n",
    "            for j in range(m):\n",
    "                x, y = bikes[j]\n",
    "                dis.append([abs(a - x) + abs(b - y), i, j])\n",
    "\n",
    "        dis.sort()\n",
    "\n",
    "        ans = [-1] * n\n",
    "        used = [0] * m\n",
    "        for _, i, j in dis:\n",
    "            if ans[i] == -1 and used[j] == 0:\n",
    "                used[j] = 1\n",
    "                ans[i] = j\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 优化\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "\n",
    "        dis = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a, b = workers[i]\n",
    "            for j in range(m):\n",
    "                x, y = bikes[j]\n",
    "                dis[abs(a - x) + abs(b - y)].append([i, j])\n",
    "\n",
    "        ans = [-1] * n\n",
    "        used = [0] * m\n",
    "        for key in sorted(list(dis.keys())):\n",
    "            for i, j in sorted(dis[key]):\n",
    "                if ans[i] == -1 and used[j] == 0:\n",
    "                    used[j] = 1\n",
    "                    ans[i] = j\n",
    "                    \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        record = collections.defaultdict(list)\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                distance = abs(workers[i][0]-bikes[j][0]) + abs(workers[i][1]-bikes[j][1])\n",
    "                record[distance].append([i, j])\n",
    "\n",
    "        res = [0 for _ in range(n)]\n",
    "        visited_w = set()\n",
    "        visited_b = set()\n",
    "        for key in sorted(record.keys()):\n",
    "            record[key].sort(key = lambda x:(x[0], x[1]))\n",
    "            if len(visited_w) == n:\n",
    "                break\n",
    "            # print(key, record[key])\n",
    "            for num in record[key]:\n",
    "                if num[0] not in visited_w and num[1] not in visited_b:\n",
    "                    res[num[0]] = num[1]\n",
    "                    visited_w.add(num[0])\n",
    "                    visited_b.add(num[1])\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        h = list()\n",
    "        for i, w in enumerate(workers):\n",
    "            for j, b in enumerate(bikes):\n",
    "                heappush(h, (abs(w[0] - b[0]) + abs(w[1] - b[1]), i, j))\n",
    "        \n",
    "        ans = dict()\n",
    "        seen_w = set()\n",
    "        seen_b = set()\n",
    "        while h:\n",
    "            _, w, b = heappop(h)\n",
    "            if w in seen_w or b in seen_b: continue\n",
    "            seen_w.add(w)\n",
    "            seen_b.add(b)\n",
    "            ans[w] = b\n",
    "        \n",
    "        return [b for _, b in sorted(ans.items())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        pq = []\n",
    "\n",
    "        for i in range(len(workers)):\n",
    "            for j in range(len(bikes)):\n",
    "                w_i, w_j = workers[i]\n",
    "                b_i, b_j = bikes[j]\n",
    "                dist = abs(w_i - b_i) + abs(w_j - b_j)\n",
    "                heapq.heappush(pq, (dist, i, j)) # dis, worker, bike\n",
    "        \n",
    "        res = [-1] * len(workers)\n",
    "        used_bike = set()\n",
    "        used_worker = set()\n",
    "        found_num = 0\n",
    "        while found_num < len(workers):\n",
    "            tmp = heapq.heappop(pq)\n",
    "            #print(tmp)\n",
    "            if tmp[1] not in used_worker and tmp[2] not in used_bike:\n",
    "                res[tmp[1]] = tmp[2]\n",
    "                found_num += 1\n",
    "                used_bike.add(tmp[2])\n",
    "                used_worker.add(tmp[1])\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m, n = len(bikes), len(workers)\n",
    "        distances = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                distance = abs(workers[j][0] - bikes[i][0]) + abs(workers[j][1] - bikes[i][1])\n",
    "                heapq.heappush(distances, (distance, j, i))\n",
    "        \n",
    "        seen_workers = set()\n",
    "        seen_bikes = set()\n",
    "        ret = [0] * n\n",
    "        while distances:\n",
    "            distance, worker, bike = heapq.heappop(distances)\n",
    "            if worker in seen_workers or bike in seen_bikes:\n",
    "                continue\n",
    "            ret[worker] = bike\n",
    "            seen_bikes.add(bike)\n",
    "            seen_workers.add(worker)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n, m = len(workers), len(bikes)\n",
    "        ans = [0] * n\n",
    "        heap = []\n",
    "        for i, (x_w, y_w) in enumerate(workers):\n",
    "            for j, (x_b, y_b) in enumerate(bikes):\n",
    "                heappush(heap, (abs(x_w - x_b) + abs(y_w - y_b), i, j))\n",
    "        vis_w = [False] * n\n",
    "        vis_b = [False] * m\n",
    "        while heap:\n",
    "            _, cur_w, cur_b = heappop(heap)\n",
    "            if vis_w[cur_w] or vis_b[cur_b]:\n",
    "                continue\n",
    "            vis_b[cur_b] = True\n",
    "            vis_w[cur_w] = True\n",
    "            ans[cur_w] = cur_b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m, n = len(bikes), len(workers)\n",
    "        distances = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                distance = abs(workers[j][0] - bikes[i][0]) + abs(workers[j][1] - bikes[i][1])\n",
    "                heapq.heappush(distances, (distance, j, i))\n",
    "        \n",
    "        seen_workers = set()\n",
    "        seen_bikes = set()\n",
    "        ret = [0] * n\n",
    "        while distances:\n",
    "            distance, worker, bike = heapq.heappop(distances)\n",
    "            if worker in seen_workers or bike in seen_bikes:\n",
    "                continue\n",
    "            ret[worker] = bike\n",
    "            seen_bikes.add(bike)\n",
    "            seen_workers.add(worker)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n, m = len(workers), len(bikes)\n",
    "        heap = []\n",
    "        def distance(l, k):\n",
    "            return abs(workers[l][0] - bikes[k][0]) + abs(workers[l][1] - bikes[k][1])\n",
    "        \n",
    "        workers_set, bikes_set = set(), set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                heapq.heappush(heap, (distance(i, j), i, j))\n",
    "        \n",
    "        res = [0] * n\n",
    "        while len(workers_set) < n:\n",
    "            dist, w, b = heapq.heappop(heap)\n",
    "            if w not in workers_set and b not in bikes_set:\n",
    "                res[w] = b \n",
    "                workers_set.add(w)\n",
    "                bikes_set.add(b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        h = []\n",
    "        for i, (wx, wy) in enumerate(workers):\n",
    "            for j, (bx, by) in enumerate(bikes):\n",
    "                h.append((abs(wx-bx)+abs(wy-by), i, j))\n",
    "        \n",
    "        heapq.heapify(h)\n",
    "\n",
    "        n = len(workers)\n",
    "\n",
    "        answer = [-1]*n\n",
    "        wlen = 0\n",
    "        bvis = set()\n",
    "        while h:\n",
    "            _, i, j = heapq.heappop(h)\n",
    "            if answer[i] != -1:\n",
    "                continue\n",
    "            if j in bvis:\n",
    "                continue\n",
    "            bvis.add(j)\n",
    "            answer[i] = j\n",
    "            wlen += 1\n",
    "            if wlen == n:\n",
    "                return answer\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        res = {}\n",
    "        workset = set()\n",
    "        bikeset = set()\n",
    "        m = len(bikes)\n",
    "        n = len(workers)\n",
    "        from heapq import heapify, heappush, heappop\n",
    "        myHeap = []\n",
    "\n",
    "        def mhtDis(worker, bike):\n",
    "            return abs(worker[0]-bike[0])+abs(worker[1]-bike[1])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                heappush(myHeap,(mhtDis(workers[j],bikes[i]),j,i))\n",
    "        while len(res) != n:\n",
    "            dis, workerID, bikeID = heappop(myHeap)\n",
    "            if bikeID in bikeset or workerID in workset:\n",
    "                continue\n",
    "            else:\n",
    "                bikeset.add(bikeID)\n",
    "                workset.add(workerID)\n",
    "                res[workerID] = bikeID\n",
    "        final = []\n",
    "        for i in range(n):\n",
    "            final.append(res[i])\n",
    "        return final\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        h = []\n",
    "        for i, (wx, wy) in enumerate(workers):\n",
    "            for j, (bx, by) in enumerate(bikes):\n",
    "                h.append((abs(wx-bx)+abs(wy-by), i, j))\n",
    "        \n",
    "        heapq.heapify(h)\n",
    "\n",
    "        n = len(workers)\n",
    "\n",
    "        answer = [-1]*n\n",
    "        wlen = 0\n",
    "        bvis = set()\n",
    "        while h:\n",
    "            _, i, j = heapq.heappop(h)\n",
    "            if answer[i] != -1:\n",
    "                continue\n",
    "            if j in bvis:\n",
    "                continue\n",
    "            bvis.add(j)\n",
    "            answer[i] = j\n",
    "            wlen += 1\n",
    "            if wlen == n:\n",
    "                return answer\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        def calculate_distance(workerLoc: List[int], bikeLoc: List[int]) -> int:\n",
    "            return abs(workerLoc[0] - bikeLoc[0]) + abs(workerLoc[1] - bikeLoc[1])\n",
    "        \n",
    "        worker_bike_map = []\n",
    "\n",
    "        heap = []\n",
    "        for workerIdx, workerLoc in enumerate(workers):\n",
    "            curr_worker_bike_map = []\n",
    "            for bikeIdx, bikeLoc in enumerate(bikes):\n",
    "                distance = calculate_distance(workerLoc, bikeLoc)\n",
    "                heapq.heappush(curr_worker_bike_map, (distance, workerIdx, bikeIdx))\n",
    "            heapq.heappush(heap, heapq.heappop(curr_worker_bike_map))\n",
    "            worker_bike_map.append(curr_worker_bike_map)\n",
    "        \n",
    "        workerStatus = [-1] * len(workers)\n",
    "        bikeStatus = [False] * len(bikes)\n",
    "        while heap:\n",
    "            distance, workerIdx, bikeIdx = heapq.heappop(heap)\n",
    "            if not bikeStatus[bikeIdx]:\n",
    "                bikeStatus[bikeIdx] = True\n",
    "                workerStatus[workerIdx] = bikeIdx\n",
    "            else:\n",
    "                closed = heapq.heappop(worker_bike_map[workerIdx])\n",
    "                heapq.heappush(heap, closed)\n",
    "        return workerStatus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        def calculate_distance(workerLoc: List[int], bikeLoc: List[int]) -> int:\n",
    "            return abs(workerLoc[0] - bikeLoc[0]) + abs(workerLoc[1] - bikeLoc[1])\n",
    "        \n",
    "        worker_bike_map = []\n",
    "\n",
    "        heap = []\n",
    "        for workerIdx, workerLoc in enumerate(workers):\n",
    "            curr_worker_bike_map = []\n",
    "            for bikeIdx, bikeLoc in enumerate(bikes):\n",
    "                distance = calculate_distance(workerLoc, bikeLoc)\n",
    "                heapq.heappush(curr_worker_bike_map, (distance, workerIdx, bikeIdx))\n",
    "            heapq.heappush(heap, heapq.heappop(curr_worker_bike_map))\n",
    "            worker_bike_map.append(curr_worker_bike_map)\n",
    "        \n",
    "        workerStatus = [-1] * len(workers)\n",
    "        bikeStatus = [False] * len(bikes)\n",
    "        while heap:\n",
    "            distance, workerIdx, bikeIdx = heapq.heappop(heap)\n",
    "            if not bikeStatus[bikeIdx]:\n",
    "                bikeStatus[bikeIdx] = True\n",
    "                workerStatus[workerIdx] = bikeIdx\n",
    "            else:\n",
    "                closed = heapq.heappop(worker_bike_map[workerIdx])\n",
    "                heapq.heappush(heap, closed)\n",
    "        return workerStatus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "\n",
    "        pairs = []\n",
    "        heap = []\n",
    "        for i in range(m):\n",
    "            pairs.append([])\n",
    "            for j in range(n):\n",
    "                dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])\n",
    "                pairs[i].append((dis, i, j))\n",
    "            pairs[i].sort(reverse=True)\n",
    "            heapq.heappush(heap, pairs[i].pop())\n",
    "        \n",
    "        bikes_with_worker = [False] * n\n",
    "        output = [-1] * m\n",
    "        while heap:\n",
    "            dis, i, j = heapq.heappop(heap)\n",
    "            if not bikes_with_worker[j]:\n",
    "                bikes_with_worker[j] = True\n",
    "                output[i] = j\n",
    "            else:\n",
    "                heapq.heappush(heap, pairs[i].pop())\n",
    "        \n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def find_distance(worker_loc, bike_loc):\n",
    "            return abs(worker_loc[0] - bike_loc[0]) + abs(worker_loc[1] - bike_loc[1])\n",
    "        \n",
    "        worker_to_bike_list, pq = [], []\n",
    "        \n",
    "        for worker, worker_loc in enumerate(workers):\n",
    "            curr_worker_pairs = []\n",
    "            for bike, bike_loc in enumerate(bikes):\n",
    "                distance = find_distance(worker_loc, bike_loc)\n",
    "                curr_worker_pairs.append((distance, worker, bike))\n",
    "            \n",
    "            curr_worker_pairs.sort(reverse=True)\n",
    "            heapq.heappush(pq, curr_worker_pairs.pop())\n",
    "            worker_to_bike_list.append(curr_worker_pairs)\n",
    "            \n",
    "        bike_status = [False] * len(bikes)\n",
    "        worker_status = [-1] * len(workers)\n",
    "        \n",
    "        while pq:\n",
    "            distance, worker, bike = heapq.heappop(pq)\n",
    "            \n",
    "            if not bike_status[bike]:\n",
    "                bike_status[bike] = True\n",
    "                worker_status[worker] = bike\n",
    "            else:\n",
    "                next_closest_bike = worker_to_bike_list[worker].pop()\n",
    "                heapq.heappush(pq, next_closest_bike)\n",
    "        \n",
    "        return worker_status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        def calculate_distance(workerLoc, bikeLoc):\n",
    "            return abs(workerLoc[0] - bikeLoc[0]) + abs(workerLoc[1] - bikeLoc[1])\n",
    "        \n",
    "        worker_bike = []\n",
    "        heap = []\n",
    "        for worker, workerLoc in enumerate(workers):\n",
    "            curr_worker_bike = []\n",
    "            for bike, bikeLoc in enumerate(bikes):\n",
    "                distance = calculate_distance(workerLoc, bikeLoc)\n",
    "                curr_worker_bike.append((distance, worker, bike))\n",
    "            curr_worker_bike.sort(reverse=True)\n",
    "            heapq.heappush(heap, curr_worker_bike.pop())\n",
    "            worker_bike.append(curr_worker_bike)\n",
    "        \n",
    "        worker_status = [-1] * len(workers)\n",
    "        bike_status = [False] * len(bikes)\n",
    "        while heap:\n",
    "            distance, worker, bike = heapq.heappop(heap)\n",
    "            if not bike_status[bike]:\n",
    "                bike_status[bike] = True\n",
    "                worker_status[worker] = bike\n",
    "            else:\n",
    "                closed_bike = worker_bike[worker].pop()\n",
    "                heapq.heappush(heap, closed_bike)\n",
    "        \n",
    "        return worker_status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        dist =[]\n",
    "\n",
    "        for i,a in enumerate(workers):\n",
    "            for j,b in enumerate(bikes):\n",
    "                dist.append((abs(a[0]-b[0])+abs(a[1]-b[1]),i,j))\n",
    "        \n",
    "        dist.sort()\n",
    "        ans =[-1]*len(workers)\n",
    "        visted_w, visted_b = set(),set()\n",
    "\n",
    "        for _,m,n in dist:\n",
    "            if m not in visted_w and n not in visted_b:\n",
    "                ans[m]=n\n",
    "                visted_w.add(m)\n",
    "                visted_b.add(n)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def find_distance(worker_loc, bike_loc):\n",
    "            return abs(worker_loc[0] - bike_loc[0]) + abs(worker_loc[1] - bike_loc[1])\n",
    "        \n",
    "        all_triplets = []\n",
    "        for worker, worker_loc in enumerate(workers):\n",
    "            for bike, bike_loc in enumerate(bikes):\n",
    "                distance = find_distance(worker_loc, bike_loc)\n",
    "                all_triplets.append((distance, worker, bike))\n",
    "        \n",
    "        all_triplets.sort()\n",
    "\n",
    "        bike_status = [False] * len(bikes)\n",
    "        worker_status = [-1] * len(workers)\n",
    "\n",
    "        pair_count = 0\n",
    "\n",
    "        for distance, worker, bike in all_triplets:\n",
    "            if worker_status[worker] == -1 and not bike_status[bike]:\n",
    "                bike_status[bike] = True\n",
    "                worker_status[worker] = bike \n",
    "                pair_count += 1\n",
    "\n",
    "                if pair_count == len(workers):\n",
    "                    return worker_status\n",
    "        return worker_status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        store = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                store.append((abs(workers[i][0]-bikes[j][0])+abs(workers[i][1]-bikes[j][1]), i, j))\n",
    "        store.sort()\n",
    "        work_assigned = set()\n",
    "        bike_assigned = set()\n",
    "        res = [0]*m\n",
    "        for item in store:\n",
    "            if item[1] not in work_assigned and item[2] not in bike_assigned:\n",
    "                work_assigned.add(item[1])\n",
    "                bike_assigned.add(item[2])\n",
    "                res[item[1]] = item[2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        dists = []\n",
    "        for i, w in enumerate(workers):\n",
    "            for j, b in enumerate(bikes):\n",
    "                dists.append(((abs(w[0] - b[0]) + abs(w[1] - b[1])), i, j))\n",
    "        dists.sort()\n",
    "        worker_set = set()\n",
    "        bike_set = set()\n",
    "        res = [0] * len(workers)\n",
    "        for _, w, b in dists:\n",
    "            if w not in worker_set and b not in bike_set:\n",
    "                res[w] = b\n",
    "                worker_set.add(w)\n",
    "                bike_set.add(b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for i, (wx, wy) in enumerate(workers):\n",
    "            for j, (bx, by) in enumerate(bikes):\n",
    "                ans.append((abs(wx-bx)+abs(wy-by),i,j))\n",
    "        ans.sort()\n",
    "        wset, bset = set(), set()\n",
    "        res = []\n",
    "        for d, i, j in ans:\n",
    "            if i not in wset and j not in bset:\n",
    "                wset.add(i)\n",
    "                bset.add(j)\n",
    "                res.append((i,j))\n",
    "        res.sort()\n",
    "        return [x[1] for x in res]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        distances = []\n",
    "        for i, (x, y) in enumerate(workers):\n",
    "            for j, (bx, by) in enumerate(bikes):\n",
    "                mandis = abs(x-bx) + abs(y-by)\n",
    "                distances.append((mandis, i, j))\n",
    "        \n",
    "        distances.sort()\n",
    "        bikes_taken = set()\n",
    "        ans = [-1] * len(workers)\n",
    "\n",
    "        for dis, w, b in distances:\n",
    "            if ans[w] == -1 and b not in bikes_taken:\n",
    "                ans[w] = b\n",
    "                bikes_taken.add(b)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        nums = []\n",
    "        for i, w in enumerate(workers):\n",
    "            for j, b in enumerate(bikes):\n",
    "                nums.append((abs(w[0] - b[0]) + abs(w[1] - b[1]), i, j))\n",
    "        \n",
    "        nums.sort()\n",
    "        vis_w, vis_b = set(), set()\n",
    "        res = [0] * n \n",
    "        for _, w, b in nums:\n",
    "            if w not in vis_w and b not in vis_b:\n",
    "                res[w] = b \n",
    "                vis_w.add(w)\n",
    "                vis_b.add(b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        array = []\n",
    "\n",
    "        for i,a in enumerate(workers):\n",
    "            for j,b in enumerate(bikes):\n",
    "                array.append((abs(a[0]-b[0])+abs(a[1]-b[1]),i,j))\n",
    "\n",
    "        visitedworker = set()\n",
    "        visitedbike = set()\n",
    "        res = [0]*len(workers)\n",
    "\n",
    "        array = sorted(array)\n",
    "\n",
    "        for _,a,b in array:\n",
    "            if a not in visitedworker and b not in visitedbike:\n",
    "                res[a] = b\n",
    "                visitedworker.add(a)\n",
    "                visitedbike.add(b)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "\n",
    "        array = []\n",
    "\n",
    "        for i, a in enumerate(workers):\n",
    "            for j, b in enumerate(bikes):\n",
    "                array.append((abs(a[0]-b[0]) + abs(a[1]-b[1]), i, j))\n",
    "        array = sorted(array)\n",
    "\n",
    "        work_set, bike_set = set(), set()\n",
    "        res = [0]*len(workers)\n",
    "\n",
    "        for _,a,b in array:\n",
    "            if a not in work_set and b not in bike_set:\n",
    "                res[a] = b;work_set.add(a);bike_set.add(b)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        array = []\n",
    "\n",
    "        for i, a in enumerate(workers):\n",
    "            for j, b in enumerate(bikes):\n",
    "                array.append((abs(a[0]-b[0]) + abs(a[1]-b[1]), i, j))\n",
    "        array = sorted(array)\n",
    "\n",
    "        work_set, bike_set = set(), set()\n",
    "        res = [0]*len(workers)\n",
    "\n",
    "        for _,a,b in array:\n",
    "            if a not in work_set and b not in bike_set:\n",
    "                res[a] = b;work_set.add(a);bike_set.add(b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        dist =[]\n",
    "\n",
    "        for i,a in enumerate(workers):\n",
    "            for j,b in enumerate(bikes):\n",
    "                dist.append((abs(a[0]-b[0])+abs(a[1]-b[1]),i,j))\n",
    "        \n",
    "        dist = sorted(dist)\n",
    "        ans =[-1]*len(workers)\n",
    "        visted_w, visted_b = set(),set()\n",
    "\n",
    "        for _,m,n in dist:\n",
    "            if m not in visted_w and n not in visted_b:\n",
    "                ans[m]=n\n",
    "                visted_w.add(m)\n",
    "                visted_b.add(n)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        def calx(a,b,x,y):\n",
    "            return abs(x-a)+abs(y-b)\n",
    "        m,n=len(workers),len(bikes)\n",
    "        q=[]\n",
    "        for i in range(m):\n",
    "            a,b=workers[i]\n",
    "            for j in range(n):\n",
    "                c,d=bikes[j]\n",
    "                heapq.heappush(q,[calx(a,b,c,d),i,j])\n",
    "        ans=[-1]*m\n",
    "        #print(q)\n",
    "        k=0\n",
    "        s=set()\n",
    "        while k<n and q:\n",
    "            d,i,j=heapq.heappop(q)\n",
    "            #print(d,i,j)\n",
    "            if ans[i]!=-1 or j in s:\n",
    "                continue\n",
    "            s.add(j)\n",
    "            ans[i]=j\n",
    "            k+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        def distance(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "        \n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        q = [[distance(workers[x], bikes[y]), x, y] for y in range(n) for x in range(m)]\n",
    "        heapify(q)\n",
    "        seen_w = set()\n",
    "        seen_b = set()\n",
    "        ans = [0] * m\n",
    "        while q:\n",
    "            _, x, y = heappop(q)\n",
    "            if x in seen_w or y in seen_b:\n",
    "                continue\n",
    "            seen_w.add(x)\n",
    "            seen_b.add(y)\n",
    "            ans[x] = y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n, m = len(workers), len(bikes)\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])\n",
    "                heap.append([dis, i, j])\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        ans = [-1] * n\n",
    "        bike_is_used = [False] * m\n",
    "        while heap:\n",
    "            while heap and (ans[heap[0][1]] != -1 or bike_is_used[heap[0][2]]):\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                ans[heap[0][1]] = heap[0][2]\n",
    "                bike_is_used[heap[0][2]] = True\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n, m = len(workers), len(bikes)\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])\n",
    "                heap.append([dis, i, j])\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        ans = [-1] * n\n",
    "        bike_is_used = [False] * m\n",
    "        cnt = 0\n",
    "        while heap:\n",
    "            while heap and (ans[heap[0][1]] != -1 or bike_is_used[heap[0][2]]):\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                ans[heap[0][1]] = heap[0][2]\n",
    "                bike_is_used[heap[0][2]] = True\n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m, n = len(workers), len(bikes)\n",
    "        ans = [-1] * m \n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res.append([abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]) , i, j])\n",
    "        res.sort()\n",
    "        chosen_workers, chosen_bikes = set(), set()\n",
    "        for dis, w, b in res:\n",
    "            if w in chosen_workers or b in chosen_bikes:\n",
    "                continue\n",
    "            ans[w] = b \n",
    "            chosen_bikes.add(b)\n",
    "            chosen_workers.add(w)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        q = [[abs(workers[x][0] - bikes[y][0]) + abs(workers[x][1] - bikes[y][1]), x, y] for y in range(n) for x in range(m)]\n",
    "        q.sort()\n",
    "        seen_w = set()\n",
    "        seen_b = set()\n",
    "        ans = [0] * m\n",
    "        for _, x, y in q:\n",
    "            if x in seen_w or y in seen_b:\n",
    "                continue\n",
    "            seen_w.add(x)\n",
    "            seen_b.add(y)\n",
    "            ans[x] = y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n=len(workers)\n",
    "        m=len(bikes)\n",
    "        arr=[]\n",
    "        for i,[x1,y1] in enumerate(workers):\n",
    "            for j,[x2,y2] in enumerate(bikes):\n",
    "                tmp=abs(x1-x2)+abs(y1-y2)\n",
    "                arr.append([tmp,i,j])\n",
    "\n",
    "        arr.sort()\n",
    "        vis=[0]*m\n",
    "       # visb=set()\n",
    "        ans=[-1]*n\n",
    "       # print(arr)\n",
    "        for d,x,y in arr:\n",
    "            if ans[x]==-1 and vis[y]==0:\n",
    "                ans[x]=y\n",
    "                vis[y]=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        dis = []\n",
    "        for i in range(n):\n",
    "            a, b = workers[i]\n",
    "            for j in range(m):\n",
    "                x, y = bikes[j]\n",
    "                dis.append([abs(a - x) + abs(b - y), i, j])#距离，工人序号，自行车序号\n",
    "        dis.sort()#距离排序\n",
    "        #print(dis)\n",
    "\n",
    "        ans = [-1] * n\n",
    "        used = [0] * m\n",
    "        for _, i, j in dis:\n",
    "            if ans[i] == -1 and used[j] == 0:#自行车j没被采用过\n",
    "                used[j] = 1#自行车j被采用\n",
    "                ans[i] = j\n",
    "                #print(ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序+贪心\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        dis = []\n",
    "        for i in range(n):\n",
    "            a, b = workers[i]\n",
    "            for j in range(m):\n",
    "                x, y = bikes[j]\n",
    "                dis.append([abs(a - x) + abs(b - y), i, j])\n",
    "\n",
    "        dis.sort()\n",
    "\n",
    "        ans = [-1] * n\n",
    "        used = [0] * m\n",
    "        for _, i, j in dis:\n",
    "            if ans[i] == -1 and used[j] == 0:\n",
    "                used[j] = 1\n",
    "                ans[i] = j\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        dis = []\n",
    "        for i in range(n):\n",
    "            a, b = workers[i]\n",
    "            for j in range(m):\n",
    "                x, y = bikes[j]\n",
    "                dis.append([abs(a - x) + abs(b - y), i, j])\n",
    "        dis.sort()\n",
    "\n",
    "        ans = [-1] * n\n",
    "        used = [0] * m\n",
    "        for _, i, j in dis:\n",
    "            if ans[i] == -1 and used[j] == 0:\n",
    "                used[j] = 1\n",
    "                ans[i] = j\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:\n",
    "        m,n=len(workers),len(bikes)\n",
    "        dis=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dis.append([abs(workers[i][0]-bikes[j][0])+abs(workers[i][1]-bikes[j][1]),i,j])\n",
    "        dis=sorted(dis) ### 排序很关键（决定答案先后顺序）\n",
    "\n",
    "        ans=[-1]*m     \n",
    "        vis=[0]*n    \n",
    "        for _,i,j in dis:\n",
    "            if ans[i]==-1 and vis[j]==0:\n",
    "                ans[i]=j  \n",
    "                vis[j]=1 \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
